|
Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location. ==Algorithm== Linear probing is accomplished using two values - one as a starting value and one as an interval between successive values in modular arithmetic. The second value, which is the same for all keys and known as the ''stepsize'', is repeatedly added to the starting value until a free space is found, or the entire table is traversed. (In order to traverse the entire table the stepsize should be relatively prime to the arraysize, which is why the array size is often chosen to be a prime number.) ::newLocation = (startingValue + stepSize) % arraySize Given an ordinary hash function ''H(x)'', a linear probing function (''H(x, i)'') would be: :: Here ''H(x)'' is the starting value, ''n'' the size of the hash table, and the ''stepsize'' is ''i'' in this case. Often, the step size is one; that is, the array cells that are probed are consecutive in the hash table. Double hashing is a variant of the same method in which the step size is itself computed by a hash function. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「linear probing」の詳細全文を読む スポンサード リンク
|